/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    List<List<TreeNode>> ans = new ArrayList<List<TreeNode>>();

    // 使用栈来记录路径上的点的值
    Deque<TreeNode> stack = new ArrayDeque<TreeNode>();
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if(root!=null) stack.offerLast(root);
        dfs(root);
          for(int i=0;i<ans.size();i++){
            int sum=0;
            for(int j=0;j<ans.get(i).size();j++){
                sum+=ans.get(i).get(j).val;
            }
            if(sum==targetSum) return true;
        }
        return false;
    }

    public void dfs(TreeNode node) {
        // 如果已经得到叶子结点
        if(node == null){
            //ans.add(new ArrayList<>(stack));
            return;
        }
        if(node.left==null && node.right==null){
            ans.add(new ArrayList<>(stack));
            return;
        }
        else{
            if(node.left!=null){
            stack.offerLast(node.left);
            dfs(node.left);
            stack.pollLast();
            }
            if(node.right!=null){
            stack.offerLast(node.right);
            dfs(node.right);
            stack.pollLast();
            }
        }
    }
}